package MyStack;

import java.util.Arrays;
import java.util.Stack;

//先进后出
public class MyStack implements Operations{

    public int[] arr;

    public int size;

    public MyStack() {
        this.arr = new int[10];
    }

    @Override
    public void push(int data) {
        if (this.isFull()) {
            this.expansion();
        }

        this.arr[this.size++] = data;
    }

    public boolean isFull() {
        return this.size == arr.length;
    }

    //扩容数组
    public void expansion() {
        this.arr = Arrays.copyOf(this.arr, this.arr.length * 2);
    }

    @Override
    public int pop() {
        if (this.isEmpty()) {
            throw new EmptyStackException("栈为空，无元素删除");
        }

        int ret = this.arr[--this.size];

        return ret;
    }

    @Override
    public int peek() {
        if (this.isEmpty()) {
            throw new EmptyStackException("栈为空，无元素可取");
        }

        return this.arr[this.size - 1];
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    public void show() {
        for (int i = this.size - 1; i >= 0; i--) {
            System.out.println(this.arr[i]);
        }
        System.out.println();
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }

            if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.empty()) {
                    return false;
                }
                char ch2 = stack.peek();
                if (!((ch2 == '(' && ch == ')') || (ch2 == '[' && ch == ']') || (ch2 == '{' && ch == '}'))) {
                    return false;
                }
                stack.pop();
            }
        }

        if (!stack.empty()) {
            return false;
        } else {
            return true;
        }
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String ch = tokens[i];

            if (ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")) {
                int num1 = stack.pop();//右
                int num2 = stack.pop();//左

                switch(ch) {
                    case "+" :
                        stack.push(num2 + num1);
                        break;
                    case "-" :
                        stack.push(num2 - num1);
                        break;
                    case "*" :
                        stack.push(num2 * num1);
                        break;
                    case "/" :
                        stack.push(num2 / num1);
                        break;
                }

            } else {
                int num = Integer.parseInt(ch);
                stack.push(num);
            }
        }
        return stack.pop();
    }

    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here

        Stack<Integer> stack = new Stack<>();

        int count = 0;//popV的指针

        for (int i = 0; i < pushV.length; i++) {
            while (!stack.isEmpty()) {
                int num = stack.peek();
                if (num == popV[count]) {
                    count++;
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(pushV[i]);
            // int num = stack.peek();
            // if (num == popV[count]) {
            //     count++;
            //     stack.pop();
            // }
        }

        for (int i = count; i < popV.length; i++) {
            int num = stack.peek();
            if (num == popV[i]) {
                stack.pop();
            }
        }

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

}
